package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202412;

import java.util.Arrays;
import java.util.TreeSet;

public class leetcode20241216 {

    /**
     * 离线+有序集合+双指针
     * @param rooms
     * @param queries
     * @return
     */
    public int[] closestRoom(int[][] rooms,int[][] queries){
        // 按照size从大到小排序
        Arrays.sort(rooms,(a,b)->(b[1]-a[1]));

        int q=queries.length;
        Integer[] queryIds=new Integer[q];
        Arrays.setAll(queryIds,i->i);
        // 按照minSize从大到小排序
        Arrays.sort(queryIds,(i,j)->queries[j][1]-queries[i][1]);

        int[] ans=new int[q];
        Arrays.fill(ans,-1);
        TreeSet<Integer> roomIds=new TreeSet<>();
        int j=0;
        for(int i : queryIds){
            int preferredId=queries[i][0];
            int minSize=queries[i][1];
            while(j<rooms.length && rooms[j][1]>=minSize){
                roomIds.add(rooms[j][0]);
                j++;
            }

            int diff=Integer.MAX_VALUE;
            Integer floor=roomIds.floor(preferredId);
            if(floor!=null){
                diff=preferredId-floor;// 左边的差
                ans[i]=floor;
            }
            Integer ceiling=roomIds.ceiling(preferredId);
            if(ceiling!=null && ceiling-preferredId<diff){// 右边的差更小
                ans[i]=ceiling;
            }
        }
        return ans;
    }
}
